package semirelatedWork;

public class Heap<E extends Comparable> {
	  private java.util.ArrayList<E> items = new java.util.ArrayList<E>();

	  /** Create a default heap */
	  public Heap() {
	  }

	  /** Create a heap from an array of objects */
	  public Heap(E[] objects) {
	    for (int i = 0; i < objects.length; i++)
	      add(objects[i]);
	  }

	  /** Add a new object into the heap */
	  public void add(E newObject) {
	    items.add(newObject); 				 // Append to the end of the heap
	    int currentIndex = items.size() - 1; 

	    /* Rebuild the heap. Starting with the last item...
	     * - If the current node is larger than its parent...
	     * 		- Swap the current node with its parent
	     * 		- The current node is now one level up. */
	    while (currentIndex > 0) {
	      int parentIndex = getParentIndex(currentIndex);
	      // Swap if current > parent
	      if (items.get(currentIndex).compareTo(
	          items.get(parentIndex)) > 0) {
	        E temp = items.get(currentIndex);
	        items.set(currentIndex, items.get(parentIndex));
	        items.set(parentIndex, temp);
	      }
	      else
	        break; 

	      currentIndex = parentIndex;
	    }
	  }

	  /** Remove the root from the heap */
	  public E remove() {
	    if (items.size() == 0) return null;

	    E rootItem = items.get(0); // Element to be returned.
	    
	    /* Rebuild the heap. 
	     * - Replace the root element with the last element.
	     * - Delete the last element.
	     * - Beginning with the root... While the current element has children
	     * 		- and the current node is smaller than one of its children... 
	     * 		- Find the larger of the two children
	     * 		- Swap the current node with the larger of the two children.*/
	    items.set(0, items.get(items.size() - 1));
	    items.remove(items.size() - 1);

	    int currentIndex = 0;
	    while (currentIndex < items.size()) {		// Has children...
	      int leftChildIndex = getLeftChildIndex(currentIndex);
	      int rightChildIndex = getRightChildIndex(currentIndex);

	      // Find the maximum between two children
	      if (leftChildIndex >= items.size()) break; // We're sorted. Stop.
	      int maxIndex = leftChildIndex;	    // Default assumption. Left is bigger
	      if (rightChildIndex < items.size()) { // Prevent IndexOutOfBounds exception.
	    	  									// Compare.
	        if (items.get(maxIndex).compareTo(items.get(rightChildIndex)) < 0) {
	          maxIndex = rightChildIndex;
	        }
	      }

	      // Swap current node with child, if necessary.
	      if (items.get(currentIndex).compareTo(items.get(maxIndex)) < 0) {
	        E temp = items.get(maxIndex);
	        items.set(maxIndex, items.get(currentIndex));
	        items.set(currentIndex, temp);
	        currentIndex = maxIndex;
	      }
	      else
	        break; // We're sorted. Stop.
	    }

	    return rootItem;
	  }

	  /** Get the number of nodes in the tree */
	  public int getSize() {
	    return items.size();
	  }
	  
	  private int getParentIndex(int currentIndex){
		  return (currentIndex - 1) / 2;
	  }
	  
	  private int getLeftChildIndex(int currentIndex){
		  return (2 * currentIndex + 1);
	  }
	  
	  private int getRightChildIndex(int currentIndex){
		  return (2 * currentIndex + 2);
	  }
	}
